class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        memo = {}
        def dp(i,j):
            if (i,j) in memo:
                return memo[i,j]
            if j == len(p):
                return i == len(s)
            
            match = i < len(s) and p[j] in {'.', s[i]}
            if j + 1 < len(p) and p[j+1] == '*':
                memo[i,j] = dp(i, j+2) or (match and dp(i+1,j) )
            else:
                memo[i,j] = (match and dp(i+1, j+1) )
                
            return memo[i,j]
            
        return dp(0,0)
                